This invention relates to communications networks. More particularly, it relates to bandwidth allocation in a network controlled by a central traffic scheduler, and to methods and embodiments of a scheduling algorithm that improves throughput of asynchronous services.
Radio Local Area Networks (LAN) typically cover an area of technology where the computer industry and the wireless communications industry merge. Conventional computer networking has relied on wired LANs, typically packet-switched and targeted for data transfer. By contrast, wireless networking, and in particular cellular networking, has relied on wide area networks, typically circuit-switched and targeted for voice transfer. Most efforts in the design of radio LANs have reused the principles that are used in wired LANs. This, however, is a questionable procedure because the environments of the wired medium and of the wireless medium differ in important ways. Moreover, multimedia communications require additional features due to the special traffic characteristics posed by data, voice and video. Finally, the residential environment has its own requirements, which can be decisive for the design of the system. Almost one hundred percent of the computer networks today use a wired infrastructure. The wired medium can range from a simple twisted pair to an optical fiber. Due to its shielded and controllable environment, the wired medium is characterized by low interference levels and stable propagation conditions. Consequently, the wired medium has potential for high to very high data rates. Because of the latter, all participants in wired LANs typically share this single medium. The medium constitutes a single channel, which is used by only a single one of a number of different users at any given time. Time-division multiplexing (TDM) is used to allow different users to access the channel at different times. The protocols for accessing wired media have been standardized by the IEEE in its 802 series. Typically, multiple access reservation techniques like carrier-sensing (e.g., Ethernet, 802.3 Carrier-Sense Multiple Access/Collision Detect (CSMA/CD)) or tokens (e.g., 802.4 token buses, or 802.5 token rings) are used to gain access to the medium. These protocols can be used in a distributed sense in that the user occupying the channel reserves the medium by its present transmission or by its token. In these schemes, every user can hear all traffic. That is, in a single LAN, all users share not only the channel, but also all of the information carried on that channel. When the number of participants grows, the LAN can be divided into smaller LANs or segments, which channels operate independently. LANs can be interconnected via bridges or routers, which form interfaces between the different local networks. These configurations result in more complex networks. For examples of this background information, reference is made to D. Bertsekas and R. Callager, Data Networks, 2nd Edition, Prentice-Hall, London, 1992. For the discussion of the residential LANs, it suffices to consider the single LAN. The LAN typically provides a connectionless packet-switched service. Each packet has a destination address (and usually a source address as well) so that each user can determine whether the packet that passes by is intended for him or not. It will be understood that the net throughput per user in a single LAN is determined by the peak data rate on the channel and by the number of users that share this channel. Even if the peak data rate is very high due to the wide bandwidth of the wireline medium, the effective user throughput can be low if the channel has to be shared among many users.
Since the type of communication that takes place over current wired LANs is asynchronous and connectionless, it is ill suited for supporting delay-critical services like voice. Voice services demand synchronous or isochronous connections, which require priority techniques in the Medium Access Control (MAC) protocols in order to give voice users precedence over non-voice users. Different studies in existing data networks have shown that this is not a trivial task. During the last several years, standards bodies in the United States and in Europe have worked on wireless LANs (WLANs). In the United States, this has resulted in the IEEE 802.11 standard (Draft standard IEEE 802.11, P802.11/D1, December 1994), whereas in Europe this has resulted in the ETSI HIPERLAN standard (ETSI, RES10/96/etr, “Radio Equipment and Systems (RES); High Performance Radio Local Area Networks (HIPERLANs), July 1996). Looking first at the IEEE 802.11 standard, as the name indicates, it is an extension of the 802 LAN standard. The wireless connection is either a radio link or an infrared link. The radio medium is the Industrial, Scientific, Medical (ISM) band at 2.4 GHz. However, for a single radioLAN, only a 1–2 Mb/s channel is available at any given time. This relatively narrow channel has to be shared among all participants of the radio network. Both a configuration based on a wired infrastructure and a configuration based on an ad-hoc structure have been defined. With a wired infrastructure, the radio system merely provides a wireless extension between the wired LAN and the user terminal. Fixed access points interface between the wireline domain and wireless domain. In an ad-hoc network, wireless units create their own wireless network. No wired backbone is involved at all. It is the ad-hoc nature provided with wireless communication that gives the WLANs an important advantage over wired LANs in certain applications.
To avoid interference with other networks or other applications in the 2.4 GHz ISM band, either direct-sequence spreading or slow frequency hopping is used. Access to the channel is accomplished by a special form of Carrier-Sense Multiple Access/Collision Avoidance (CSMA/CA) that provides a connectionless service. In an architecture based on a wired infrastructure, the fixed part takes the role of a central controller, which schedules all traffic. In an ad-hoc architecture, the distributed CSMA/CA protocol provides the multiple access to the channel. All in all, the IEEE 802.11 standard is very similar to that of the wired Ethernet, with the wire being replaced by a 1 Mb/s radio channel. It will be understood that the effective user throughput decreases quickly when the number of participants increases. In addition, since the spreading factor for Direct Sequence Spread Spectrum (DSSS) is only 11 and the hop rate for Frequency Hopping Spread Spectrum (FHSS) is only on the order of 10 to 20 hops/s, little immunity is provided against interference in the ISM band. Different networks can theoretically coexist in the same area (different networks either use different DSSS carrier frequencies of which seven are defined, or use different FHSS hop sequences), thereby increasing the aggregate throughput. In fact, in A. Kamerman, “Spread-Spectrum Techniques Drive WLAN Performance,” Microwaves &: RF, September 1996, pp. 109–114, it was claimed that the aggregate throughput, defined as the average throughput per user times the number of collocated users (not necessarily participating in the same network), can never exceed 4–6 Mb/s with either technology. For collocating different networks under the IEEE 802.11 standard it is preferred that the networks be based on a wired infrastructure: a limited number of collocated fixed access points can create their own network. A certain amount of coordination via the wired network is then possible. However, for networks based on an ad-hoc structure, this is much more difficult under IEEE 802.11 because the MAC protocol does not lend itself to this creation. Instead, units that come in range of an ad-hoc network will join an existing network and not create their own network.
HIPERLAN has followed a similar path as IEEE 802.11. The system operates in the 5.2 GHz band (not available in the United States). The standard is still under development and consists of a family of sub-standards, HIPERLAN 1 to 4. The most basic part, HIPERLAN 1 (ETSI, ETS300652, “Radio Equipment and Systems (RES); High Performance Radio Local Area Networks (HIPERLAN) Type 1; “Functional Specification”, June 1996), is similar to the IEEE 802.11 standard. Again, a single channel is used, but with a higher peak data rate of 23.5 Mb/s. A dedicated CSMA/CA scheme is used, called Elimination-Yield Non-Preemptive Priority Multiple Access (EY-NPMA) which provides a number of contention-based phases before the channel is reserved. Although the 5.2 GHz band is unlicensed in Europe, only HIPERLAN-type applications are allowed. Therefore, no special measures against unknown jammers are implemented. Different networks can coexist in the same area provided different 23 MHZ wide channels are used. Out of the 5.2 GHz, five such channels have been defined. One other interesting activity in the HIPERLAN area is the HIPERLAN 2 standardization, which concentrates on wireless Asynchronous Transfer Mode (ATM). Presumably, this wireless network will also use the 5.2 GHz band, will support peak data rates exceeding 40 Mb/s, and will use a centralized access scheme with some kind of demand assignment MAC scheme.
What the existing WLAN systems have in common with the wired LANs is that a single channel is shared among all the participants of the local network. All users share both the medium itself and all information carried over this medium. In the wired LAN, this channel encompasses the entire medium. However, this is not so in the radioLANs. In the radioLANs, the radio medium typically has a bandwidth of 80 to 100 MHZ. Due to implementation limitations and cost of the radio transceivers, and due to restrictions placed by regulatory bodies like the FCC and ETSI, it is virtually impossible to define a radio channel in the radioLAN with the same bandwidth as the radio medium. Therefore, only part of the radio medium is used in a single LAN. As a result, the peak data rate over the channel decreases. But more importantly, the effective user throughput decreases because all participants share this channel, which is now much smaller than the medium. Although the medium is divided into different channels, each of which can be used to set up a different radioLAN, in practice, only a single network covers a certain area, especially when it concerns ad-hoc networks. In radioLANs based on a wired infrastructure, the different channels can be used to create cells, each cell with its own network that is not or minimally disturbed by neighboring cells. This result is achieved at the expense of effort in planning the allocation of channels. In this way, a cellular structure is created that is similar to those encountered in cellular mobile systems. The use of different ad-hoc radio networks in the same cell, however, is prohibited, thereby limiting the attainable aggregate throughput per unit area.
Ad-hoc networks, by definition, do not rely on the support of a wired infrastructure as is commonly applied in cellular, cordless and WLAN systems. In the latter systems, access to the wired backbone is accomplished by access points or base stations. These base stations broadcast known control signals to which the portable terminals can lock. Via the control signals, incoming and outgoing calls can be established and terminals can be directed to dedicated traffic channels. In conventional wireless systems, the activities of the base stations are highly coordinated. In ad-hoc systems, the situation is completely different. Since ad-hoc systems are based on peer-to-peer connectivity, there is no difference between base stations and terminals. Terminals could of course start to operate as base stations in order to facilitate connection establishment. However, in a peer environment, it is unclear which unit should be base station, when and for how long. It is very undesirable to have each radio unit broadcast control information because it is not at all certain whether other units are around to receive this information. In addition, it consumes valuable (battery) power and creates unnecessary interference.
A system called a BLUETOOTH™ system was recently introduced to provide ad-hoc connectivity between portable devices like mobile phones, laptops, PDAs, and other nomadic devices. This system applies frequency hopping to enable the construction of low-power, low-cost radios with a small footprint. The system supports both data and voice communication. The latter is optimized by applying fast frequency hopping with a nominal rate of 800 hops/s through the entire 2.4 GHz ISM band in combination with a robust voice coding. Automatic retransmission is applied on data packets to combat packet failures due to collisions between different piconets visiting the same hop channel. Devices based on the BLUETOOTH™ system concept can create so called piconets, which consist of a master device, and one or more slave devices connected via the FH piconet channel. The FH sequence used for the piconet channel is completely determined by the address or identity of the device acting as the master. The system clock of the master device determines the phase in the hopping sequence. In the BLUETOOTH™ system, each device has a free-running system clock. The slave devices add a time offset to their clocks such that they become aligned with the clock of the master device. By using the master address to select the proper hopping sequence and by using the time offset to align to the master clock, the slave devices keep in hop synchrony to the master device; that is, master and slave devices remain in contact by hopping synchronously to the same hop frequency or hop carrier. For more details, the reader is referred to U.S. Patent Application entitled “FH piconets in an uncoordinated wireless multi-user system,” by J. C. Haartsen, U.S. patent application Ser. No. 08/932,911 filed on Sep. 18, 1997, which is hereby incorporated herein by reference in its entirety.
In order to provide both low-priority asynchronous services as well as high-priority synchronous services, in BLUETOOTH™ systems, all information transfer is controlled by the master. The master and slaves alternatively transmit and receive radio packets in a Time Division Duplex (TDD) fashion. To prevent two or more slaves from transmitting simultaneously, which would result in a packet collision and packet failure at the master receiver, the master for each packet assigns the slave that is allowed to transmit. With this polling procedure, the master can prioritize traffic flows and can allocate bandwidths between the slaves efficiently. All traffic is contention free. Polling is achieved by the rule that a slave is only allowed to transmit in the current slave-to-master slot when it has received a packet from the master in the master-to-slave slot directly preceding the current slave-to-master slot. Each packet contains a slave address with which the master addresses the slave. If the master has something to transfer to the slave, the master packet will contain a payload with slave information. This type of packet is referred to throughout this disclosure as an implicit poll and the act of sending it is called “implicitly polling”, since receipt of this packet allows the slave to respond. If the master has no information to send to the slave, it occasionally has to send a packet without a payload to the slave, just to enable the slave to send something to the master. This packet without a payload serves as a poll packet explicitly polling the slave, and the act of sending such a packet is referred to throughout the disclosure as “explicitly polling”. The polling procedure used by the master determines the bandwidth allocation given to the slaves: when a slave is polled more often, it receives more bandwidth.
In the past, several polling schemes have been considered. Round-robin schemes, in which the master consecutively polls the slaves, is optimal when the throughput and latency requirements between the slaves are uniform. Descriptions of round-robin methods can be found in “Exact Analysis of round-robin scheduling of services,” by Hodeaki Takagi, IBM J. Rs. Dev. 31, 4 (July), pp 484–488, and in “Queuing Analysis of Polling Models,” by Hodeaki Takagi, ACM Computing Surveys, Vol. 20, No. 1, March 1988. To dynamically adjust to traffic offering, exhaustive polling can be applied which means that once a slave is allowed to start transmission, it will keep sending packets until its queue is empty. Only then will the master progress to the next slave. Combinations of round-robin and exhaustive polling have been described in “Performance Evaluation of Scheduling Algorithms for Bluetooth,” by N. Johansson et al., Proc. of IFIP TC6, 5th Int'l. Conf. On Broadband Communication 1999, Hong Kong, Nov. 10–12, 1999; such combinations are denoted as fair exhaustive polling. Polling schemes so far have taken into account desired throughput, and offered load. However, they have not properly addressed latency and service priority.